#include <iostream>
#include <vector>

using namespace std;

const int MaxVertices = 100;

vector<vector<int>> AdjacencyMatrix(MaxVertices + 1, vector<int>(MaxVertices + 1, 0));
vector<bool> Visited(MaxVertices + 1, false);
int NumVertices = 0;

void DepthFirstSearch(int vertex) {
    cout << vertex << " ";
    Visited[vertex] = true;
    for (int adjacentVertex = 1; adjacentVertex <= NumVertices; ++adjacentVertex) {
        if (AdjacencyMatrix[vertex][adjacentVertex] > 0 && !Visited[adjacentVertex]) {
            DepthFirstSearch(adjacentVertex);
        }
    }
}

void DepthFirstSearchForest() {
    for (int vertex = 1; vertex <= NumVertices; ++vertex) {
        Visited[vertex] = false;
    }
    int component = 0;
    for (int vertex = 1; vertex <= NumVertices; ++vertex) {
        if (!Visited[vertex]) {
            ++component;
            cout << component << ") ";
            DepthFirstSearch(vertex);
            cout << endl;
        }
    }
}

void ReadGraph() {
    cout << "Введите количество вершин: ";
    cin >> NumVertices;
    while (NumVertices < 1 || NumVertices > MaxVertices) {
        cout << "Ошибка ввода. Пожалуйста, введите число от 1 до " << MaxVertices << ": ";
        cin >> NumVertices;
    }
    cout << "Введите матрицу смежности (0 или 1):" << endl;
    bool error = false;
    for (int u = 1; u <= NumVertices; ++u) {
        for (int v = 1; v <= NumVertices; ++v) {
            char inputChar;
            cin >> inputChar;
            if (inputChar != '0' && inputChar != '1') {
                AdjacencyMatrix[u][v] = -1;
                error = true;
            } else {
                AdjacencyMatrix[u][v] = inputChar - '0';
            }
        }
    }
    if (error) {
        cout << "Ошибка ввода. Пожалуйста, перезаполните:" << endl;
        for (int u = 1; u <= NumVertices; ++u) {
            for (int v = 1; v <= NumVertices; ++v) {
                if (AdjacencyMatrix[u][v] < 0) {
                    cout << "A[" << u << ", " << v << "] = ";
                    char inputChar;
                    cin >> inputChar;
                    while (inputChar != '0' && inputChar != '1') {
                        cout << "Ошибка ввода. Пожалуйста, введите 0 или 1:" << endl;
                        cout << "A[" << u << ", " << v << "] = ";
                        cin >> inputChar;
                    }
                    AdjacencyMatrix[u][v] = inputChar - '0';
                }
            }
        }
    }
    cout << "Ввод графа завершен." << endl << endl;
}

void ShowGraph() {
    cout << "Матрица смежности:" << endl;
    for (int u = 1; u <= NumVertices; ++u) {
        for (int v = 1; v <= NumVertices; ++v) {
            cout << AdjacencyMatrix[u][v];
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    cout << "Программа обхода графа в глубину:" << endl;
    cout << "Доступные команды:" << endl;
    cout << "CLS - Очистить экран" << endl;
    cout << "EXIT - Выйти из программы" << endl;
    cout << "READ - Ввести граф" << endl;
    cout << "SOLVE - Найти обход графа" << endl;
    cout << "NCHANGE - Изменить количество вершин" << endl;
    cout << "GCHANGE - Изменить граф" << endl;
    cout << "VIEW - Показать граф" << endl;
    cout << "Введите команду: ";
    
    string command;
    while (cin >> command) {
        if (command == "CLS") {
            system("clear");
        } else if (command == "READ") {
            ReadGraph();
        } else if (command == "SOLVE") {
            DepthFirstSearchForest();
        } else if (command == "NCHANGE") {
            cout << "Enter the new number of vertices: ";
            cin >> NumVertices;
        } else if (command == "GCHANGE") {
            cout << "Введите матрицу смежности графиков:" << endl;
            ReadGraph();
        } else if (command == "VIEW") {
            ShowGraph();
        } else if (command == "EXIT") {
            break;
        } else {
            cout << "Недопустимая команда" << endl;
        }
        cout << "Введите команду: ";
    }
    
    return 0;
}



